#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef char StackDataType;

typedef struct Stack
{
    StackDataType* data;
    int pos;
    int capacity;
}Stack;

void InitStack(Stack* ps)
{
    assert(ps);

    ps->data = (StackDataType*)malloc(sizeof(StackDataType) * 4);
    if (ps->data == NULL)
    {
        perror("InitStack()");
        exit(1);
    }
    ps->pos = 0;
    ps->capacity = 4;
}

bool StackEmpty(Stack* ps)
{
    assert(ps);

    return ps->pos == 0;
}

size_t StackSize(Stack* ps)
{
    assert(ps);

    return ps->pos;
}

void StackPush(Stack* ps, StackDataType x)
{
    assert(ps);

    if (ps->pos == ps->capacity)
    {
        StackDataType* tmp = (StackDataType*)realloc(ps->data, sizeof(StackDataType) * 2 * ps->capacity);
        if (tmp == NULL)
        {
            perror("StackPush()");
            exit(1);
        }
        ps->data = tmp;
        ps->capacity *= 2;
    }
    ps->data[ps->pos++] = x;
}

void StackPop(Stack* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));

    ps->pos--;
}

StackDataType StackTop(Stack* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));

    return ps->data[ps->pos - 1];
}

void DestroyStack(Stack* ps)
{
    free(ps->data);
    ps->data = NULL;
    ps->pos = 0;
    ps->capacity = 0;
}

bool isValid(char* s)
{
    Stack T;
    InitStack(&T);

    while (*s)
    {
        if (*s == '(' || *s == '{' || *s == '[')
        {
            StackPush(&T, *s);
            s++;
        }
        else
        {
            if (StackEmpty(&T))
            {
                DestroyStack(&T);
                return false;
            }
            else
            {
                char tmp = StackTop(&T);
                StackPop(&T);
                if (tmp != '{' && *s == '}' ||
                    tmp != '(' && *s == ')' ||
                    tmp != '[' && *s == ']')
                {
                    DestroyStack(&T);
                    return false;
                }
                else
                {
                    s++;
                }
            }
        }
    }
    bool ret = StackEmpty(&T);
    DestroyStack(&T);
    return ret;
}